package sort.堆排序;

public class HeapSort {
    /**
     * 选择排序优化，寻找最大值交给堆，重复这个过程最终完成排序
     */
    public static void test() {
        int[] arrays = {14,0,8,35,97,24,78,56,27};
        // 返回数组长度
        int length = arrays.length;
        buildHeap(length,arrays);
        int k = length;
        while (k > 1) {
            int temp = arrays[0];
            arrays[0] = arrays[k-1];
            arrays[k-1] = temp;
            k--;
            shiftDown(0,arrays,k);
        }
        for (int array : arrays) {
            System.out.println(array);
        }
    }
    // 判断是不是叶子节点
    public static Boolean isLeaf(int length, int index) {
        return index >= (length / 2) && (index < length);
    }
    // 返回左孩子节点索引
    public static int leftChild(int pos) {
        return 2*pos + 1;
    }
    // 返回右孩子节点索引
    public static int rightChild(int pos) {
        return 2*pos + 2;
    }
    // 对完全二叉树的所有根节点进行遍历，建堆
    public static void buildHeap(int length, int[] arrays) {
        for (int i = length / 2 -1; i >= 0 ; i--) {
            // 从倒数第二层开始向上逐层遍历
            shiftDown(i,arrays,length);
        }
    }
    // 下拉函数
    public static void shiftDown(int i,int[] arrays,int length) {
        // 不是叶子节点就循环
        while (!isLeaf(length,i)) {
            int l = leftChild(i);
            int r = rightChild(i);
            if ((r<length)&&(arrays[l]<arrays[r])) {
                l = r;
            }
            if (arrays[i] > arrays[l]) {
                return;
            }
            int temp = arrays[i];
            arrays[i] = arrays[l];
            arrays[l] = temp;
            i = l;
        }
    }
    // 取最大值函数
    public static int getMax(int length,int[] arrays) {
        if (length <= 0) {
            System.out.println("数组为空");
            return 100;
        }
        int temp = arrays[0];
        arrays[0] = arrays[length-1];
        arrays[length-1] = temp;
        if (length != 0) {shiftDown(0,arrays,length);}
        // 返回最大值
        return arrays[length-1];
    }
}
